這題要在一個旋轉排序且包含重複元素的陣列中找最小值,並減少操作步驟,從題目以知這個陣列是經過多次旋轉,所以不能簡單地線性搜尋最小值,要考慮用有效率的二分法處理。
思路:
這題類似「在旋轉排序數組中找最小值」,但因為數組中可能會出現重複元素,所以讓二分查找變更複雜,一般情況,二分法是基於數組的有序性來切割,但如果陣列有重複值,某些情況下,沒法直接通過比較中間值跟兩端值來判斷哪邊是有序的,這就要多考慮一些細節。
步驟:
二分法重點,每次取中間點 mid,如果 nums[mid] < nums[right],表示最小值在左半邊或者就是 mid,因為右邊是有序的,最小值一定在左邊,如果 nums[mid] > nums[right],那最小值一定在右半邊,因為左邊是有序的,最小值不可能在這邊,如果 nums[mid] == nums[right],就沒辦法判斷哪部分是有序,這時可以把 right 減 1,繼續縮小範圍,處理重複元素,當出現 nums[mid] == nums[right] 時,兩端相等,不確定最小值在哪邊,可以把 right 減一,這樣可以排除右邊的一個元素且不會錯過最小值。
程式碼:
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
#如果中間值比右邊小,說明最小值在左邊
if nums[mid] < nums[right]:
right = mid
#如果中間值比右端大,最小值在右邊
elif nums[mid] > nums[right]:
left = mid + 1
#nums[mid] == nums[right] 時,不能確定哪邊有序,右指針減 1 繼續
else:
right -= 1
return nums[left]
解釋:
設初始範圍,left 和 right 分別指向數組的開始跟結束,二分法循環,每次迴圈,算中間位置 mid,再把中間值跟右邊界值比較,如果 nums[mid] < nums[right],表最小值在 mid 左邊,把 right 設成 mid,如果 nums[mid] > nums[right],表最小值在 mid 右邊,把 left 設成 mid + 1,如果 nums[mid] == nums[right],無法確定最小值在哪邊,需要把 right 減少 1,繼續找,結束條件, left 和 right 相等,最小值就是 nums[left]。
心得:
解這道題讓我對二分查找的理解比較全面,尤其是處理帶有重複元素的情況,我學會靈活用移動指針的方法來縮小範圍也體會到即使題目看似跟經典問題類似,但加一點變化(重複元素),解法可能需要調整才能達到最佳效率,這道題目的設計不僅要求對演算法有深刻的理解,還鍛煉問題分解和應變能力。